using System;
using System.Collections.Generic;
using Newtonsoft.Json;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0117. 填充每个节点的下一个右侧节点指针 II")]
    public class No0117_Connect : AbsBaseTestItem
    {
        /*
        给定一个二叉树
        填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
        初始状态下，所有 next 指针都被设置为 NULL。

        进阶：
            你只能使用常量级额外空间。
            使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
        提示：
            树中的节点数小于 6000
            -100 <= node.val <= 100
        */

        public class Node
        {
            public int val;
            public Node left;
            public Node right;
            public Node next;

            public Node() { }

            public Node(int _val)
            {
                val = _val;
            }

            public Node(int _val, Node _left, Node _right, Node _next)
            {
                val = _val;
                left = _left;
                right = _right;
                next = _next;
            }
        }

        public override void OnTest()
        {
            Node root = new Node(1)
            {
                left = new Node(2)
                {
                    left = new Node(4),
                    right = new Node(5),
                },
                right = new Node(3)
                {
                    right = new Node(7),
                },
            };

            var rnode = JsonConvert.DeserializeObject<Node>(JsonConvert.SerializeObject(root));
            rnode.left.next = rnode.right;
            rnode.left.left.next = rnode.left.right;
            rnode.left.right.next = rnode.right.right;

            Assert.TestExe(Connect, root, rnode);
        }

        public Node Connect(Node root)
        {
            Node last = null, nextStart = null;
            void handle(Node p)
            {
                if (last != null)
                {
                    last.next = p;
                }
                if (nextStart == null)
                {
                    nextStart = p;
                }
                last = p;
            }
            if (root == null)
            {
                return null;
            }
            Node start = root;
            while (start != null)
            {
                last = null;
                nextStart = null;
                for (Node p = start; p != null; p = p.next)
                {
                    if (p.left != null)
                    {
                        handle(p.left);
                    }
                    if (p.right != null)
                    {
                        handle(p.right);
                    }
                }
                start = nextStart;
            }
            return root;
        }
    }
}
